﻿namespace TSP.Algorithm;

internal class Population
{
    public Population(List<Tour> tours)
    {
        P = tours;
        MaxFit = CalcMaxFit();
    }

    internal static Population Randomized(Tour tours, int n)
    {
        var tmp = new List<Tour>(n);
        for (int i = 0; i < n; ++i)
            tmp.Add(tours.Shuffle());
        return new Population(tmp);
    }

    private List<Tour> P { get; set; }

    private double MaxFit { get; set; }

    private Random R { get; set; } = new Random();

    private double CalcMaxFit()
    {
        return P.Max(t => t.Fitness);
    }

    private Tour Select()
    {
        while (true)
        {
            int i = R.Next(0, TSPCalculator.PopSize);
            if (R.NextDouble() < P[i].Fitness / MaxFit)
                return new Tour(P[i].CitySeries);
        }
    }

    private Population GenNewPop(int n)
    {
        var p = new List<Tour>(n);
        for (int i = 0; i < n; ++i)
        {
            Tour t = Select().Crossover(Select());
            foreach (City c in t.CitySeries)
                t = t.Mutate();
            p.Add(t);
        }
        return new Population(p);
    }

    private Population Elite(int n)
    {
        var best = new List<Tour>(n);
        var tmp = new Population(P);
        for (int i = 0; i < n; ++i)
        {
            best.Add(tmp.FindBest());
            tmp = new Population(tmp.P.Except(best).ToList());
        }
        return new Population(best);
    }

    internal Tour FindBest()
    {
        foreach (Tour t in P)
        {
            if (t.Fitness == MaxFit)
                return t;
        }
        throw new Exception("算法异常终止");
    }

    internal Population Evolve()
    {
        Population best = Elite(TSPCalculator.Elitism);
        Population np = GenNewPop(TSPCalculator.PopSize - TSPCalculator.Elitism);
        return new Population(best.P.Concat(np.P).ToList());
    }
}

